package com.csdemos.algs.graphs;

import java.util.LinkedList;

public class BFS {
	
	private static final int NIL = -1;
	private static final int WHITE = 0;
	private static final int GRAY = 1;
	private static final int BLACK = 2;

	public static String PrintPath(Graph graph, int s, int v) {
		StringBuilder builder = new StringBuilder();
		int[] P = BFS_BuildP(graph, s);
		path(graph, s, v, P, builder);
		return builder.toString();
	}
	
	private static void path(Graph graph, int s, int v, int[] P, StringBuilder buffer) {
		if (v == s) {
			buffer.append(s);
		} else {
			if (P[v] == NIL) {
				buffer.append("Path from ").append(s).append(" to ").append(v).append(" is absent");
			} else {
				path(graph, s, P[v], P, buffer);
				buffer.append(v).append(" ");
			}
		}
	}
	
	private static int[] BFS_BuildP(Graph graph, int s) {
		LinkedList<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		int n = graph.getVertexs().length;
		int[] color = new int[n];
		int[] P = new int[n];
		int u;
		while (!Q.isEmpty()) {
			u = Q.pollFirst();
			for (int v : graph.getAdjecents(u)) {
				if (color[v] == WHITE) {
					color[v] = GRAY;
					P[v] = u;
					Q.add(v);
				}
			}
			color[u] = BLACK;
		}
		return P;
	}
}
